Images, such as charts, drawings, and pictures, may be represented as a two-dimensional matrix of picture elements (pixels). The spatial resolution and tone level for each pixel are chosen to correspond to the particular output device used. For example, typical computer monitors display images at 75 dots per inch (DPI) and have 256 levels of intensity for each color. Such monitors use the additive primary colors, red, green, and blue (RGB), which can be combined to produce millions of colors and also black.
Typical hardcopy output devices, such as inkjet printers, are binary devices, meaning that for each pixel or possible dot location on the printed medium they can only print at two levels: on or off. Therefore, some means must be provided to convert the monitor-based version of the image (256 tone levels per color), or another version of the color image, to the binary version (2 levels per color). These conversion methods are commonly referred to as halftoning. Halftoning methods are described in the book Digital Halftoning, by Robert Ulichney, The MIT Press, 1987, incorporated herein by reference.
One major approach to halftoning is error diffusion. The decision about whether or not to print a dot is based not only on the “ideal” intensity (i.e., one of the 256 possible intensities) for that pixel, but on what has happened before for previously processed pixels.
It is assumed in the following explanation that there are 256 pixel intensities that range between 0 and 255. In conventional error diffusion, at each point where a dot may be printed, the original image pixel intensity between 0 to 255, plus accumulated error, is compared to a previously chosen threshold value. If the image pixel intensity is greater than the threshold value, a dot (255 intensity) is assigned to that pixel. If not, no dot (0 intensity) is assigned. In either case, the intensity difference between the actual dot value assigned (0 or 255) and the ideal image pixel intensity plus accumulated error for that point is derived, and this difference becomes an error term that is “diffused” to other subsequently processed pixels. In other words, the diffused error term is added to the image pixel intensity plus the accumulated error of other subsequently processed pixels, and this total resultant image pixel intensity is then compared against the error diffusion threshold to determine whether a dot should be printed. The parameters in error diffusion halftoning that have the most visual effects on the final outcome of the printed output are the thresholds, the error weightings and the direction of the error diffusion.
Typically, an error diffusion threshold value is static, e.g., 50 percent of the maximum theoretical image pixel intensity. For example, if there are 256 tone levels (0 and 255) per pixel, a level of 128 may be chosen as the threshold value. Improvements to the quality of the printed output may be achieved, however, by randomly varying the threshold value as described in Digital Halftoning, by Robert Ulichney, The MIT Press, 1987, page 265.
In addition, typical error diffusion techniques use constant weighting factors to compute the proportion of the error that is diffused to each surrounding pixel. A well known error diffusion technique is described by R. Floyd and L. Steinberg in the paper Adaptive Algorithm for Spatial Grey Scale, SID Int'l. Sym. Digest of Tech. Papers, pp. 36-37 (1975), incorporated herein by reference. The Floyd and Steinberg error diffusion technique diffuses the error into a set of four surrounding pixels. Error diffusion with higher than four terms can also be used. U.S. Pat. No. 5,313,287 to David Barton, assigned to the present assignee and incorporated herein by reference, discloses another error diffusion technique.
Another type of error diffusion method, known as tone dependent error diffusion, varies the error diffusion threshold value and/or the error weightings according to the tone or intensity of the pixel being processed. Tone dependent error diffusion is described in the articles “Reduction of Artifacts in Error Diffusion by Means of Input-Dependent Weights,” by Eschbach, E., Journal of Electronic Imaging, vol. 2(4), October 1993, and “Adaptive Filtering for Error Diffusion Quality Improvement,” by Shu, J., SID Digest of Technical Papers, May 1995, as well as U.S. Pat. Nos. 5,737,453 and 5,757,976, all of which are incorporated herein by reference. Tone dependent error diffusion techniques are typically monochromatic.
When printing a color image, dots for multiple colors, such as cyan, magenta, and yellow, are printed in various combinations to achieve the desired color tones to reproduce the original color image. Many known error diffusion methods operate on one color plane (e.g., cyan, magenta, or yellow) at a time. These types of error diffusion methods strive to generate a visually pleasing pattern of dots (i.e., dispersed dots) for each separate color, independent of the pattern of dots for the remaining colors. Due to random chance, these overlapping color dot patterns inevitably result in two or more dots of different colors overlapping or being adjacent to one another, as shown in FIG. 1, which is perceived by the human eye as a clumping of dots.
FIG. 1 illustrates an example of a prior art multi-colored dot pattern using magenta dots 4 and cyan dots 6. The overall tone is light blue. When the cyan and magenta planes overlap, non-pleasing dot patterns due to adjacent cyan and magenta dots (such as at location 7) can be formed due to random chance.
Other known error diffusion methods operate on multiple color planes at the same time, which is known as plane dependency, such as the method described in U.S. application Ser. No. 08/880,475, entitled “Correlating Cyan and Magenta Planes for Error Diffusion Halftoning” by Jay S. Gondek, filed Jun. 3, 1997, having the same assignee, and which is incorporated herein by reference. Multiple color planes, such as cyan and magenta, are correlated to create dot patterns that do not fall on top of one another up to a combined 100 percent fill. Consequently, the occurrence of darker “blue” dots (cyan overlapping magenta creates dark blue) is avoided, which also fills in white space that would otherwise contributed to the perception of graininess. Thus, a more visually pleasing patterning of dots is created.
FIG. 2 illustrates an example of a dot pattern of cyan and magenta dots printed using a plane dependent error diffusion method. As can be seen, FIG. 2 is an improvement over FIG. 1 because there are no adjacent or overlapping cyan and magenta dots.
However, as can be seen in FIG. 2, a drawback of plane dependent halftoning is that the relative spatial placement of the dots in light tones is not optimized. Consequently, in light or mid tones, patterns can develop in the printed output. These patterns occur because of the way the error can “cascade” through the image to produce curved lines of printed dots. These anomalies are often referred to as “worms” because they can resemble small thin worms in the image.
As discussed above, while tone dependent error diffusion may be used to generate a pleasing pattern of dots, tone dependent error diffusion is monochromatic. Consequently, the use of tone dependent error diffusion with a color image results in an image that, while each color may independently have a pleasing pattern, when combined the colors randomly overlap.
Accordingly, there is a need for a color halftoning method that provides a printed output with the plurality of colors that are correlated so as to produce uniform patterning without unintentionally overlap of the colors.